package com.likeycy.my;

import com.likeycy.my.heap.BinaryHeap;
import com.likeycy.my.printer.BinaryTrees;

import java.util.Comparator;

/**
 * @ClassName: TestBinaryHeap
 * @Description: 测试二叉堆
 * @Author: sodagreen
 * @Date: 2021/3/27 3:38
 * @Version: 1.0
 */
public class TestBinaryHeap {

    /**
     * 测试 二叉堆 增删改查功能
     */
    static void testBinaryHeapByCrud() {
        BinaryHeap<Integer> heap = new BinaryHeap<>();
        heap.add(72);
        heap.add(62);
        heap.add(82);
        heap.add(60);
        heap.add(11);
        heap.add(55);
        heap.add(999);
        System.out.println(heap.size());
        BinaryTrees.println(heap);

        System.out.println(heap.remove());
        BinaryTrees.println(heap);

        System.out.println(heap.replace(12));
        BinaryTrees.println(heap);
    }

    /**
     * 测试批量建堆
     */
    public static void testBinaryHeapByHeapify() {
        Integer[] array = {75, 40, 5, 59, 47, 99, 29, 3, 1, 90, 4, 84, 78, 52, 30, 67, 62, 19};
        BinaryHeap<Integer> heap = new BinaryHeap<>(array);

        BinaryTrees.println(heap);

    }

    public static void testDiy() {
        Integer[] array = {75, 40, 5, 59, 47, 99, 29, 3, 1, 90, 4, 84, 78, 52, 30, 67, 62, 19};
        BinaryHeap<Integer> heap = new BinaryHeap<>(array, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {

                return o2 - o1;
            }
        });

        BinaryTrees.println(heap);

    }

    public static void testBinaryHeapByTopKey() {
        Integer[] array = {18, 65, 80, 25, 91, 33, 15
                , 49, 87, 38, 97, 82, 78, 14, 6, 95
                , 8, 36, 86, 44, 35, 57, 42, 9, 83
                , 31, 68, 64, 41, 69, 92, 24, 37, 55};
        BinaryHeap<Integer> heap = new BinaryHeap<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });

        // 找出最大的前 K 个数
        int topKey = 3;
        for (int i = 0; i < array.length; i++) {
            // 将前 K 个数添加到小顶堆
            if (heap.size() < topKey) {
                heap.add(array[i]);
            } else { // 如果是第 k+1 个元素
                // 如果第 k+n 个元素大于堆顶的元素，那么就替换
                if (array[i] > heap.get()) {
                    heap.replace(array[i]);
                }
            }
        }

        BinaryTrees.println(heap);

    }

    public static void main(String[] args) {

        testBinaryHeapByTopKey();

    }

}
